1482. Умножение матриц
Пусть даны две
прямоугольные матрицы A и B размерности m
× n и n × q
соответственно:
, 
Тогда матрица C
размерностью m × q называется их произведением:
где:
, (i = 1, 2, …, m; j
= 1, 2, …, q)
Операция
умножения двух матриц выполнима только в том случае, если число столбцов в
первом сомножителе равно числу строк во втором; в этом случае говорят, что
форма матриц согласована.
Задано две
матрицы A и B. Найти их произведение.
Вход. В первой строке задано 2 натуральных числа na и ma – размерность матрицы A. В последующих na строках задано по ma чисел – элементы aij матрицы A. В (na + 2)-й строке задано 2
натуральных числа nb и mb – размерность матрицы B. В
последующих nb строках
задано по mb чисел –
элементы bij матрицы B.
Размерность матриц не превышает 100×100, все элементы матриц целые числа,
не превышающие по модулю 100.
Выход. В первой строке вывести размерность итоговой матрицы C: nс и mc. В последующих nс
строках вывести через пробел по mc
чисел – соответствующие элементы cij
матрицы C. Если умножать матрицы нельзя в первой и единственной строке вывести
число -1.
|
Пример
входа |
Пример
выхода |
|
2 3 1 3 4 5 -2 3 3 3 1 3 2 2 1 3 0 -1 1 |
2 3 7 2 15 1 10 7 |
РЕШЕНИЕ
алгебра
Анализ алгоритма
Перемножаем
матрицы, используя формулу:
, где i = 1, 2, …, m; j
= 1, 2, …, q.
Пример
В
примере приведено произведение матриц:
Реализация алгоритма
Матрицы A, B, C
будем хранить соответственно в двумерных массивах a, b, c.
#define MAX 100
int a[MAX][MAX], b[MAX][MAX],
c[MAX][MAX];
Читаем входные
матрицы A и B.
scanf("%d %d",&na,&ma);
for(i = 0; i < na; i++)
for(j = 0; j < ma; j++) scanf("%d",&a[i][j]);
scanf("%d %d",&nb,&mb);
for(i = 0; i < nb; i++)
for(j = 0; j < mb; j++) scanf("%d",&b[i][j]);
Обнулим результирующую матрицу С.
memset(c,0,sizeof(c));
Если ma не равно nb, то
матрицы нельзя перемножать.
if (ma != nb)
{
printf("-1\n");
return 0;
}
Перемножаем матрицы, используя выше
приведенную формулу.
for (i = 0; i < na; i++)
for (j = 0; j < mb; j++)
for (k = 0; k < ma; k++)
c[i][j] += a[i][k] * b[k][j];
Выводим результирующую матрицу С.
printf("%d %d\n",na,mb);
for(i = 0; i < na; i++)
{
for(j = 0; j
< mb; j++)
printf("%d
",c[i][j]);
printf("\n");
}
Реализация алгоритма –
двойной указатель
#include <stdio.h>
#define MAX 100
int na, ma, nb, mb;
int **a, **b, **c;
void Read(int **&matr, int n, int m)
{
matr = new int*[n];
for (int i = 0; i < n; i++)
{
matr[i] = new int[m];
for (int j = 0; j < m; j++)
scanf("%d", &matr[i][j]);
}
}
void Mult(int **a, int **b, int **&c, int m, int n, int q)
{
c = new int*[m];
for (int i = 0; i < m; i++)
{
c[i] = new int[q];
for (int j = 0; j < q; j++)
{
c[i][j] = 0;
for (int k = 0; k
< n; k++)
c[i][j] += a[i][k] * b[k][j];
}
}
}
void Print(int **a, int n, int m)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
printf("%d ", a[i][j]);
printf("\n");
}
}
int main(void)
{
scanf("%d %d", &na, &ma);
Read(a,
na, ma);
scanf("%d %d", &nb, &mb);
Read(b,
nb, mb);
if (ma != nb)
{
printf("-1\n");
return 0;
}
Mult(a, b, c, na, ma, mb);
printf("%d %d\n", na, mb);
Print(c,
na, mb);
return 0;
}
Java реализация
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int na = con.nextInt();
int ma = con.nextInt();
int a[][] = new int[na][ma];
for (int i = 0; i < na; i++)
for (int j = 0; j < ma; j++)
a[i][j] = con.nextInt();
int nb = con.nextInt();
int mb = con.nextInt();
int b[][] = new int[nb][mb];
for (int i = 0; i < nb; i++)
for (int j = 0; j < mb; j++)
b[i][j] = con.nextInt();
con.close();
if (ma != nb)
{
System.out.println(-1);
return;
}
int c[][] = new int[na][mb];
for (int i = 0; i < na; i++)
for (int j = 0; j < mb; j++)
for (int k = 0; k < ma; k++)
c[i][j] += a[i][k] * b[k][j];
System.out.println(na + " " + mb);
for (int i = 0; i < na; i++)
{
for (int j = 0; j < mb; j++)
System.out.print(c[i][j] + " ");
System.out.println();
}
}
}